class Solution:
    def countPalindromicSubsequence(self, s: str) -> int:
        stat0 = [False] * 26  # 前面是否已经有字母i
        stat1 = [[False] * 26 for _ in range(26)]  # 字母i之后有哪些字母
        stat2 = [[False] * 26 for _ in range(26)]  # 字母i之间有哪些字母
        for ch in s:
            i = ord(ch) - 97
            for j in range(26):
                stat2[i][j] = stat1[i][j] or stat2[i][j]
            for j in range(26):
                if stat0[j] is True:
                    stat1[j][i] = True
            stat0[i] = True

        ans = 0
        for i in range(26):
            for j in range(26):
                ans += stat2[i][j]
        return ans


if __name__ == "__main__":
    print(Solution().countPalindromicSubsequence("aabca"))  # 3
    print(Solution().countPalindromicSubsequence("adc"))  # 0
    print(Solution().countPalindromicSubsequence("bbcbaba"))  # 4
